import java.util.Arrays;

public class Solution {

    private int mod = 1000000007; 

    // 归并排序
    public int mergeSort(int left, int right, int[] array, int[] temp) {
        if (left >= right) {
            return 0;
        }

        int mid = (left + right) / 2;
        int res = (mergeSort(left, mid, array, temp) + mergeSort(mid + 1, right, array, temp)) % mod;

        for (int i = left; i <= right; i++) {
            temp[i] = array[i];
        }

        int l = left;
        int r = mid + 1;
        for (int i = left; i <= right; i++) {
            if (l == mid + 1) {
                array[i] = temp[r++];
            }
            else if (r == right + 1 || temp[l] <= temp[r]) {
                array[i] = temp[l++];
            }
            else {
                array[i] = temp[r++];
                res += mid - l + 1;
            }
        }

        return res % mod;
    }

    public int InversePairs(int [] array) {

        int[] temp = new int[array.length];
        return mergeSort(0, array.length - 1, array, temp);
        
    }
}
